package eighthweek;

import fourthweek.Array.ArrayUnorderedList;
import fourthweek.UnorderedListADT;

public class AVLTree<T extends Comparable<T>> {
    protected AVLTreeNode<T> root;

    public AVLTree() {
        root = null;
    }

    public AVLTree(T element) {
        if (!(element instanceof Comparable))
            throw new NonComparableElementException("AVLTreeNode");

        root = new AVLTreeNode<T>(element);
    }

    //高度
    public int height() {
        return height(root);
    }
    private int height(AVLTreeNode<T> tree) {
        if (tree != null)
            return tree.height;

        return 0;
    }

    //查找元素
    public T find(T targetElement) {
       AVLTreeNode<T> current = findNode(targetElement, root);

        if (current == null)
            throw new ElementNotFoundException("AVLTree");

        return (current.getElement());
    }
    private AVLTreeNode<T> findNode(T targetElement, AVLTreeNode<T> next) {
        if (next == null)
            return null;
        if (next.getElement().equals(targetElement))
            return next;
        AVLTreeNode<T> temp = findNode(targetElement, next.getLeft());
        if (temp == null)
            temp = findNode(targetElement, next.getRight());

        return temp;
    }

    //判断是否为空
    public boolean isEmpty() {
        return (root == null);
    }

    //找寻最小值
    public T findMin(AVLTreeNode<T> tree) {
        T result = null;

        if (tree.getElement() == null)
            throw new EmptyCollectionException("AVLTree");
        else {
            if (tree.getLeft() == null) {
                result = tree.getElement();
            } else {
                AVLTreeNode<T> current = tree.getLeft();
                while (current.getLeft() != null) {
                    current = current.getLeft();
                }
                result = current.getElement();
            }
        }
        return result;
    }

    public T findMax(AVLTreeNode<T> tree) {
        T result = null;

        if (tree.getElement() == null)
            throw new EmptyCollectionException("AVLTree");
        else {
            if (tree.getRight() == null) {
                result = tree.getElement();
            } else {
                AVLTreeNode<T> current = tree.getRight();
                while (current.getRight() != null) {
                    current = current.getRight();
                }
                result = current.getElement();
            }
        }
        return result;
    }
    private AVLTreeNode<T> leftLeftSpin(AVLTreeNode<T> node) {
        AVLTreeNode<T> temp;

        temp = node.left;
        node.left = temp.right;
        temp.right = node;

        node.height = Math.max(height(node.left), height(node.right)) + 1;
        temp.height = Math.max( height(temp.left), node.height) + 1;

        return temp;
    }
    private AVLTreeNode<T> rightRightSpin(AVLTreeNode<T> node) {
        AVLTreeNode<T> temp;

        temp = node.right;
        node.right = temp.left;
        temp.left = node;

        node.height = Math.max( height(node.left), height(node.right)) + 1;
        temp.height = Math.max( height(temp.right), node.height) + 1;

        return temp;
    }
    private AVLTreeNode<T> leftRightSpin(AVLTreeNode<T> node) {
        node.left = rightRightSpin(node.left);

        return leftLeftSpin(node);
    }
    private AVLTreeNode<T> rightLeftSpin(AVLTreeNode<T> node) {
        node.right = leftLeftSpin(node.right);

        return rightRightSpin(node);
    }
    public void addElement(T key) {
        root = addElement(root, key);
    }
    private AVLTreeNode<T> addElement(AVLTreeNode<T> tree, T element) {

        if (!(element instanceof Comparable)) {
            throw new NonComparableElementException("AVLTreeNode");
        }

        if (tree == null) {
            tree = new AVLTreeNode<T>(element, null, null);
            if (tree==null) {
                throw new EmptyCollectionException("EmptyCollectionException");
            }
        } else {

            if (element.compareTo(tree.getElement()) < 0) {
                tree.left = addElement(tree.left, element);
                // 插入节点后，若AVL树失去平衡，则进行相应的调节。
                if (height(tree.right) - height(tree.left) == -2) {
                    if (element.compareTo(tree.left.getElement()) < 0)
                        tree = leftLeftSpin(tree);
                    else
                        tree = leftRightSpin(tree);
                }
            } else if (element.compareTo(tree.getElement()) >= 0) {
                tree.right = addElement(tree.right, element);
                // 插入节点后，若AVL树失去平衡，则进行相应的调节。
                if (height(tree.left) - height(tree.right) == -2) {
                    if (element.compareTo(tree.right.getElement()) > 0)
                        tree = rightRightSpin(tree);
                    else
                        tree = rightLeftSpin(tree);
                }
            }
        }

        tree.height = Math.max( height(tree.left), height(tree.right)) + 1;

        return tree;
    }

    //删除二叉树中全部元素
    public void removeAllElement(){
        AVLTreeNode<T> root = null;
        this.root = root;
    }

    public void removeElement(T key) {
        AVLTreeNode<T> z;
        if ((z = findNode(key,root)) != null)
            root = removeElement(root, z);
    }
    private AVLTreeNode<T> removeElement(AVLTreeNode<T> tree, AVLTreeNode<T> node) {
        if (tree==null || node ==null)
            return null;
        if (node.element.compareTo(tree.element) < 0) {
            tree.setLeft(removeElement(tree.getLeft(), node));
            if (height(tree.getRight()) - height(tree.getLeft()) == 2) {
                AVLTreeNode<T> r =  tree.getRight();
                if (height(r.getLeft()) > height(r.getRight()))
                    tree = rightLeftSpin(tree);
                else
                    tree = rightRightSpin(tree);
            }
        } else if (node.element.compareTo(tree.element) > 0) {
            tree.setRight(removeElement(tree.getRight(), node));
            if (height(tree.getLeft()) - height(tree.getRight()) == 2) {
                AVLTreeNode<T> l =  tree.getLeft();
                if (height(l.getRight()) > height(l.getLeft()))
                    tree = leftRightSpin(tree);
                else
                    tree = leftLeftSpin(tree);
            }
        } else {
            if ((tree.getLeft() != null) && (tree.getRight() != null)) {
                if (height(tree.getLeft()) > height(tree.getRight())) {
                    AVLTreeNode<T> max = (AVLTreeNode<T>)findMax(tree.getLeft());
                    tree.element = max.element;
                    tree.setLeft(removeElement(tree.getLeft(), max));
                } else {
                    AVLTreeNode<T> min = (AVLTreeNode<T>)findMax(tree.getRight());
                    tree.element = min.element;
                    tree.setRight(removeElement(tree.getRight(), min));
                }
            } else {
                tree = (tree.getLeft()!=null) ? tree.getLeft() : tree.getRight();
            }
        }
        return tree;
    }
    //前序输出
    public void toPreString(){
        preOrder(root);
    }
    private void preOrder(AVLTreeNode<T> root){
        if(null!= root){
            System.out.print(root.getElement() + "\t");
            preOrder(root.getLeft());
            preOrder(root.getRight());
        }
    }

    //中序输出
    public void toInString(){
        inOrder(root);
    }
    private void inOrder(AVLTreeNode<T> root) {
        if (null != root) {
            inOrder(root.getLeft());
            System.out.print(root.getElement() + "\t");
            inOrder(root.getRight());
        }
    }

    //后序输出
    public void toPostString(){
        postOrder(root);
    }
    private void postOrder(AVLTreeNode<T> root) {
        if (null != root) {
            postOrder(root.getLeft());
            postOrder(root.getRight());
            System.out.print(root.getElement() + "\t");
        }
    }

    //层序输出递归
    public void toLevelString(){
        if(root == null)
            return;
        int height = root.height;
        for(int i = 1; i <= height; i++){
            levelOrder(root,i);
        }
    }
    private void levelOrder(AVLTreeNode<T> root,int level){
        if(root == null || level < 1){
            return;
        }
        if(level == 1){
            System.out.print(root.getElement() + "\t");
            return;
        }
        levelOrder(root.getLeft(),level - 1);
        levelOrder(root.getRight(),level - 1);
    }
    //树状输出AVL树
    public String toString(){
        UnorderedListADT<AVLTreeNode<T>> nodes = new ArrayUnorderedList<AVLTreeNode<T>>();
        UnorderedListADT<Integer> levelList = new ArrayUnorderedList<Integer>();

        AVLTreeNode<T> current;
        String result = "";
        int printDepth = this.height();
        int possibleNodes = (int) Math.pow(2, printDepth + 1);
        int countNodes = 0;

        nodes.addToRear(root);
        Integer currentLevel = 0;
        Integer previousLevel = -1;
        levelList.addToRear(currentLevel);

        while (countNodes < possibleNodes) {
            countNodes = countNodes + 1;
            current = nodes.removeFirst();
            currentLevel = levelList.removeFirst();
            if (currentLevel > previousLevel) {
                result = result + "\n\n";
                previousLevel = currentLevel;
                for (int j = 0; j < ((Math.pow(2, (printDepth - currentLevel))) - 1); j++)
                    result = result + " ";
            } else {
                for (int i = 0; i < ((Math.pow(2,
                        (printDepth - currentLevel + 1)) - 1)); i++) {
                    result = result + " ";
                }
            }
            if (current != null) {
                result = result + (current.getElement()).toString();
                nodes.addToRear(current.getLeft());
                levelList.addToRear(currentLevel + 1);
                nodes.addToRear(current.getRight());
                levelList.addToRear(currentLevel + 1);
            } else {
                nodes.addToRear(null);
                levelList.addToRear(currentLevel + 1);
                nodes.addToRear(null);
                levelList.addToRear(currentLevel + 1);
                result = result + " ";
            }
        }
        return result;
    }
}